import java.util.Stack;

public class Sort {
    /**
     * 插入排序
     */
    public static void insertOder(int[] array) {
        //从第二个元素开始，第一个元素默认已接排序
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];   //当前需要的元素
            int j = i - 1;//已排序的最后一个元素
            //从后往前移找到最合适的位置
            for (; j >= 0; j--) {
                if (array[j] > temp) {
                    //将不合适的后移
                    array[j + 1] = array[j];
                } else {
                    // array[j+1]=temp;
                    break;
                }
            }
            //插入
            array[j + 1] = temp;
        }
    }

    public static void shellSort(int[] arrya) {
        int gap = arrya.length;
        while (gap > 1) {
            gap /= 2;
            shell(arrya, gap);
        }

    }

    private static void shell(int[] arrya, int gap) {
        for (int i = gap; i < arrya.length; i++) {
            int temp = arrya[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (arrya[j] > temp) {
                    arrya[j + gap] = arrya[j];
                } else {
                    break;
                }
            }
            arrya[j + gap] = temp;
        }
    }

    /**
     * 选择排序
     */
    public void seeleckOrder(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int mindex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < mindex) {
                    mindex = j;
                }
            }
            swap(array, i, mindex);
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void heapSort(int[] array) {
        creatheap(array);
        int end = array.length - 1;
        while (end > 0) {
            swap(array, 0, end);
            siftdown(array, 0, end);
            end--;
        }
    }

    private static void siftdown(int[] array, int parent, int lenth) {
        int child = parent * 2 + 1;
        while (child < lenth) {
            if (child + 1 < lenth && array[child + 1] > array[child]) {
                child++;
            }
            if (array[parent] < array[child]) {
                swap(array, parent, child);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    private static void creatheap(int[] array) {
        for (int panrent = (array.length - 1 - 1) / 2; panrent >= 0; panrent--) {
            siftdown(array, panrent, array.length);
        }
    }

    /**
     * 冒泡排序
     */
    public static void bubble(int[] array) {
        //几个数字就会少一个循环，5个数字4次循环
        for (int i = 0; i < array.length - 1; i++) {
            //优化，如果没有进入循环说明已经有顺序了
            boolean flag = false;
            //每一次交换比前一次少一次
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }

    public static void quikSort(int[] array) {
        quik(array, 0, array.length - 1);
    }

    private static void quik(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        if (end - start >= 15) {
            insertOderUse(array, start, end);
            return;
        }
        int index = midThree(array, start, end);
        swap(array, start, index);
        int pivod = partition1(array, start, end);
        quik(array, start, pivod - 1);
        quik(array, pivod + 1, end);

    }

    private static int partition(int[] array, int start, int end) {
        int i = start;
        int temp = array[start];
        while (start < end) {
            while (start < end && array[end] >= temp) {
                end--;
            }
            while (start < end && array[start] <= temp) {
                start++;
            }
            swap(array, start, end);
        }
        swap(array, i, start);
        return start;
    }

    private static int partition1(int[] array, int start, int end) {
        int temp = array[start];
        while (start < end) {
            while (start < end && array[end] >= temp) {
                end--;
            }
            array[start] = array[end];
            while (start < end && array[start] <= temp) {
                start++;
            }
            array[end] = array[start];
        }
        array[start] = temp;
        return start;
    }

    private static int partition2(int[] array, int left, int right) {
        int prev = left;
        int cur = left + 1;
        while (cur <= right) {
            if (array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array, cur, prev);
            }
            cur++;
        }
        swap(array, prev, left);
        return prev;
    }

    private static int midThree(int[] array, int start, int end) {
        int mid = (start + end) / 2;
        if (array[start] > array[end]) {
            if (array[mid] > array[end]) {
                return mid;
            } else if (array[mid] > array[start]) {
                return start;
            } else {
                return end;
            }
        } else {
            if (array[mid] > array[end]) {
                return end;
            } else if (array[mid] > array[start]) {
                return mid;
            } else {
                return start;
            }
        }
    }

    //由于插入排序越有顺序速度越快，快排和插入一起使用会更快
    public static void insertOderUse(int[] array, int left, int right) {
        //从第二个元素开始，第一个元素默认已接排序
        for (int i = left + 1; i <= right; i++) {
            int temp = array[i];   //当前需要的元素
            int j = i - 1;//已排序的最后一个元素
            //从后往前移找到最合适的位置
            for (; j >= left; j--) {
                if (array[j] > temp) {
                    //将不合适的后移t
                    array[j + 1] = array[j];
                } else {
                    // array[j+1]=temp;
                    break;
                }
            }
            //插入
            array[j + 1] = temp;
        }
    }

    public static void quikOrderNor(int[] array) {
        int start = 0;
        int end = array.length - 1;
        Stack<Integer> stack = new Stack<>();
        int priod = partition(array, start, end);
        if (priod > start + 1) {
            stack.push(start);
            stack.push(priod - 1);
        }
        if (priod < end - 1) {
            stack.push(priod + 1);
            stack.push(end);

        }
        while (!stack.isEmpty()) {
            end = stack.pop();
            start = stack.pop();
            priod = partition(array, start, end);
            if (priod > start + 1) {
                stack.push(start);
                stack.push(priod - 1);
            }
            if (priod < end - 1) {
                stack.push(priod + 1);
                stack.push(end);

            }
        }

    }

    /**
     * 归并排序
     */
    public static void mergeSort(int[] array) {
        mergeChild(array, 0, array.length);
    }

    private static void mergeChild(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        //分解
        mergeChild(array, left, mid);
        mergeChild(array, mid + 1, right);
        //合并
        merge(array, left, mid, right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int l1 = left, e1 = mid, l2 = mid + 1, e2 = right;
        int[] tempArray = new int[right - left + 1];
        int k = 0;
        while (e1 >= l1 && e2 >= l2) {
            if (array[l1] > array[l2]) {
                tempArray[k++] = array[l2++];
            } else {
                tempArray[k++] = array[l1++];
            }

        }
        while (l1 <= e1) {
            tempArray[k++] = array[l1++];
        }
        while (l2 <= e2) {
            tempArray[k++] = array[l2++];
        }
        for (int i = 0; i < k; i++) {
            array[i+left] = tempArray[i];
        }
    }
    public static void mergerNor(int[] array){
        int gap=1;
        while(gap<array.length){
            for (int i = 0; i <array.length; i+=2*gap) {
               int left=i;
               int mid=left+gap-1;
               if (mid>=array.length){
                   mid=array.length-1;
               }
               int right=mid+gap;
               if (right>=array.length-1){
                   right=array.length-1;
               }
               merge(array,left,mid,right);
            }
            gap*=2;
        }
    }
    private static void conrtSort(int[] array){
         int max=array[0];
         int min=array[0];
        for (int i = 0; i <array.length ; i++) {
            if (array[i]<min){
                min=array[i];
            }
            if (array[i]>max){
                max=array[i];
            }
        }
        int len=max-min+1;
        int[] tempArray=new int[len];
        //遍历原来的数组，得到计数数组
        for (int i = 0; i <array.length ; i++) {
            int index=array[i]-min;
            tempArray[index]++;
        }
        int k=0;
        //遍历计数数组
        for (int i = 0; i < len; i++) {
          while (tempArray[i]!=0){
              array[k]=i+min;
              k++;
              tempArray[i]--;
          }
        }
    }

}

